package pro.softzhang.algo.lc500;

import pro.softzhang.algo.common.TreeNode;
import pro.softzhang.algo.flag.difficulty.DRed;
import pro.softzhang.algo.flag.x.XOptimal;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 513. 找树左下角的值
 * https://leetcode.cn/problems/find-bottom-left-tree-value/description/
 */
@DRed
public class LC513_FindBottomLeftTreeValue {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(2, new TreeNode(1, null, null), new TreeNode(3, null, null));
        int lv = new Solution().findBottomLeftValue(root);
        System.out.println(lv);
    }

    /**
     *
     */
    static
    class Solution {
        public int findBottomLeftValue(TreeNode root) {
            Queue<TreeNode> q1 = new LinkedList<>(), q2 = new LinkedList<>();
            q1.offer(root);
            int bottomLeft = root.val;
            while (!q1.isEmpty()) {
                TreeNode node = q1.poll();
                if(node.left != null) {
                    q2.offer(node.left);
                }

                if(node.right != null) {
                    q2.offer(node.right);
                }

                if(q1.isEmpty()) {
                    q1 = q2;
                    q2 = new LinkedList<>();
                    if(!q1.isEmpty()) {
                        bottomLeft = q1.peek().val;
                    }
                }
            }
            return bottomLeft;
        }
    }

    /**
     *
     */
    @XOptimal
    static
    class Solution1 {
        public int findBottomLeftValue(TreeNode root) {
            Queue<TreeNode> q = new LinkedList<TreeNode>(){{
                offer(root);
            }};

            TreeNode node = root;
            while (!q.isEmpty()) {
                node = q.poll();
                if(node.right != null) {
                    q.add(node.right);
                }
                if(node.left != null) {
                    q.add(node.left);
                }
            }
            return node.val;
        }
    }
}